package pers.sloera.leetcode.editor.cn;

/**
 * 省份数量
 *
 * @author sloera
 * @date 2022-07-25 23:02:16
 */
class NumberOfProvinces {
    public static void main(String[] args) {
        Solution solution = new NumberOfProvinces().new Solution();
        solution.findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findCircleNum(int[][] isConnected) {
            int[] fa = new int[isConnected.length];
            int[] rank = new int[isConnected.length];
            // init
            for (int i = 0; i < fa.length; i++) {
                fa[i] = i;
                rank[i] = 1;
            }
            for (int i = 0; i < isConnected.length; i++) {
                for (int j = 0; j < isConnected[i].length; j++) {
                    if (isConnected[i][j] == 1) {
                        merge(fa, rank, i, j);
                    }
                }
            }
            int count = 0;
            for (int i = 0; i < fa.length; i++) {
                if (i == find(fa, rank, i)) {
                    count++;
                }
            }
            return count;
        }

        private int find(int[] fa, int[] rank, int i) {
            return fa[i] == i ? i : (fa[i] = fa[fa[i]]);
        }

        private void merge(int[] fa, int[] rank, int i, int j) {
            int x = find(fa, rank, i);
            int y = find(fa, rank, j);
            if (rank[x] <= rank[y]) {
                fa[x] = y; // = fa[y]
            } else {
                fa[y] = fa[x]; // = x
            }
            if (rank[x] == rank[y] && x != y) {
                rank[y]++;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
